package oj_leetcode;

import java.util.ArrayList;
import java.util.List;

public class RemoveInvalidParentheses {

    public List<String> removeInvalidParentheses(String s) {
        return removeInvalidParentheses(s, 0);
    }

    public List<String> removeInvalidParentheses(String s, int index) {
        List<String> res = new ArrayList<>();
        if (index == s.length()) {
            res.add("");
            return res;
        }
        int sum = 0;
        int start = index;
        List<Integer> right_record = new ArrayList<>();
        List<Integer> left_record = new ArrayList<>();
        while (sum >= 0 && index < s.length()) {
            char curr = s.charAt(index);
            if (curr == '(') {
                left_record.add(index);
                sum++;
            } else if (curr == ')') {
                right_record.add(index);
                sum--;
            }
            index++;
        }

        if (sum > 0) {
            // 删除-sum数目的左括号
            int pre = -2;
            for (Integer i : left_record) {
                if (i != pre + 1) {

                }
                pre = i;

            }
            return res;
        } else if (sum == 0) {
            res.add(s.substring(start));
            return res;
        } else {
            int pre = -2;
            List<String> nextRes = removeInvalidParentheses(s, index);
            for (Integer i : right_record) {
                if (i != pre + 1) {
                    String target = s.substring(start, i) + s.substring(i + 1, index);
                    for (String tmp : nextRes) {
                        res.add(target + tmp);
                    }
                }
                pre = i;
            }
            return res;
        }
    }

}
